//// A Simple Problem with Integers
//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <map>
//#include <set>
//#include <queue>
//#include <stack>
//#include <deque>
//#include <functional>
//#include <climits>
//
//#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//#define endl "\n"
//
//using namespace std;
//typedef long long ll;
//
//#define lc (2*p)
//#define rc (2*p + 1)
//
//const int N = 1e5 + 5;
//
//ll arr[N];
//
//struct node
//{
//	ll sum;
//	ll add;
//	int l;
//	int r;
//}tr[4 * N];
//
//void pushdown(int p)
//{
//	if (tr[p].add)
//	{
//		tr[lc].add += tr[p].add;
//		tr[rc].add += tr[p].add;
//		tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
//		tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
//		tr[p].add = 0;
//	}
//}
//
//void pushup(int p)
//{
//	tr[p].sum = tr[lc].sum + tr[rc].sum;
//}
//
//void change(int p, int l, int r, int k)
//{
//	if (tr[p].l >= l && tr[p].r <= r)
//	{
//		tr[p].add += k;
//		tr[p].sum += k * (tr[p].r - tr[p].l + 1);
//		return;
//	}
//
//	int mid = (tr[p].l + tr[p].r) / 2;
//	pushdown(p);
//	if (l <= mid)
//		change(lc, l, r, k);
//	if (r > mid)
//		change(rc, l, r, k);
//	pushup(p);
//}
//
//ll query(int p, int x, int y)
//{
//	if (tr[p].l >= x && tr[p].r <= y)
//		return tr[p].sum;
//
//	ll sum = 0;
//	int mid = (tr[p].l + tr[p].r) / 2;
//	pushdown(p);
//	if (x <= mid)
//		sum += query(lc, x, y);
//	if (y > mid)
//		sum += query(rc, x, y);
//	pushup(p);
//	return sum;
//}
//
//void bulid(int p, int l, int r)
//{
//	tr[p] = { arr[l], 0, l, r };
//	if (l == r)
//	{
//		return;
//	}
//
//	int mid = (l + r) / 2;
//	bulid(lc, l, mid);
//	bulid(rc, mid + 1, r);
//	pushup(p);
//}
//
//int main()
//{
//	quickio;
//	int n, q;
//	cin >> n >> q;
//
//	for (int i = 1; i <= n; i++)
//		cin >> arr[i];
//	bulid(1, 1, n);
//
//	char ch;
//	int a, b, c;
//	while (q--)
//	{
//		cin >> ch;
//
//		if (ch == 'C')
//		{
//			cin >> a >> b >> c;
//			change(1, a, b, c);
//		}
//		else
//		{
//			cin >> a >> b;
//			cout <<query(1, a, b) << endl;
//		}
//	}
//	return 0;
//}